#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 2e4 + 5;

int n, m;
int a[N], b[N], pos[N];
int l[155], r[155];
ll cnt[155];
ll ans;
ll cnt_gt(int id, int x) {
  return b + r[id] + 1 - upper_bound(b + l[id], b + r[id] + 1, x);
}
ll cnt_lt(int id, int x) {
  return lower_bound(b + l[id], b + r[id] + 1, x) - b - l[id];
}
ll sort_inb(int id) {
  cnt[id] = 0;
  rep(i, l[id], r[id]) b[i] = a[i];
  rep(i, l[id], r[id]) {
    int x = b[i];
    int j = i - 1;
    while (j >= l[id] && b[j] > x) {
      b[j + 1] = b[j];
      j--;
      cnt[id]++;
    }
    b[j + 1] = x;
  }
  return cnt[id];
}
void init() {
  int k = sqrt(n);
  rep(i, 1, n) pos[i] = (i - 1) / k + 1;
  int cnt = pos[n];
  rep(i, 1, cnt) {
    l[i] = (i - 1) * k + 1;
    r[i] = i * k;
  }
  r[cnt] = n;
  rep(i, 1, cnt) {
    ans += sort_inb(i);
    rep(j, 1, i - 1) rep(u, l[i], r[i]) ans += cnt_gt(j, a[u]);
  }
}
void change(int L, int R) {
  int id1 = pos[L], id2 = pos[R];
  if (id1 == id2) {
    ans -= cnt[id1];
    swap(a[L], a[R]);
    ans += sort_inb(id1);
    return;
  }
  ans -= cnt[id1];
  ans -= cnt[id2];
  rep(i, id1, id2 - 1) ans -= cnt_gt(i, a[R]);
  rep(i, id1 + 1, id2) ans -= cnt_lt(i, a[L]);
  if (a[L] > a[R]) ans++;
  swap(a[L], a[R]);
  ans += sort_inb(id1);
  ans += sort_inb(id2);
  rep(i, id1, id2 - 1) ans += cnt_gt(i, a[R]);
  rep(i, id1 + 1, id2) ans += cnt_lt(i, a[L]);
  if (a[L] > a[R]) ans--;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  rep(i, 1, n) cin >> a[i];
  init();
  cout << ans << endl;
  cin >> m;
  while (m--) {
    int l, r;
    cin >> l >> r;
    if (l > r) swap(l, r);
    change(l, r);
    cout << ans << endl;
  }
  return 0;
}